#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 10010;
class Solution
{
  public:
    int mem[N][3];
    int dfs(int x, int prcolor, vector<vector<int>> &costs)
    {
        if (x == costs.size())
            return 0;
        if (mem[x][prcolor] != -1)
            return mem[x][prcolor];
        int min_res = 1e9;
        for (int color = 0; color < 3; color++)
        {
            if (color != prcolor)
            {
                int current = costs[x][color] + dfs(x + 1, color, costs);
                min_res = min(current, min_res);
            }
        }
        mem[x][prcolor] = min_res;
        return min_res;
    }
    int minCost(vector<vector<int>> &costs)
    {
        if (costs.empty())
            return 0;
        int n = costs.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        // memset(mem, -1, sizeof (mem));
        // int ans1 = dfs(1, 0, costs) + costs[0][0];
        // int ans2 = dfs(1, 1, costs) + costs[0][1];
        // int ans3 = dfs(1, 2, costs) + costs[0][2];
        // return min(ans1, min(ans2, ans3));
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
        }
        int ans = min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]));
    }
};
